package cn.nju.seg.atg.util;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import cn.nju.seg.atg.model.Constraint;
import cn.nju.seg.atg.model.SimpleCFGNode;
import cn.nju.seg.atg.visitor.CFGNode;

/**
 * 涉及到路径的一些操作
 * 1. 从文件读取路径
 * 2. 从CFG生成所有路径
 * @author ChengXin
 *
 */
public class PathUtil {
	
/************************************************
 | 从文件读取执行路径								|
 | @param filePath								|
 | @return 一条路径								|
 ***********************************************/
	public static List<CFGPath> readPath(String filePath)
	{
		List<XPath> xPaths = new ArrayList<XPath>();
		PathUtil pu = new PathUtil();
		XPath xPath = pu.new XPath();
		xPaths.add(xPath);
		try{
			String str;
			BufferedReader in = new BufferedReader(new FileReader(filePath));
			// 记录分支节点的个数
			int numOfBranchNode = 0;
			while((str = in.readLine())!=null)
			{
				if (!str.equals(""))
				{
					String[] array = str.split(" ");
/*					for(int num=0;num<array.length;num++){
					    System.out.println(array[num].toString());
					}
*/
					if(array.length > 1)
					{
						numOfBranchNode++;
					}
					
					if (isInNextNodes(xPaths, array[0]))
					{
						// 未发现新路径
						int xPathsSize = xPaths.size();
						for (int i=0; i<xPathsSize; i++)
						{
							xPaths.get(i).updateAll(array);
						}
					}
					else
					{
						// 发现一条新路径
						int xPathsSize = xPaths.size();
						List<XPath> newXPaths = getNewXPaths(xPaths, array);
						int newXPathsSize = newXPaths.size();
						for (int i=0; i<newXPathsSize; i++)
						{
							xPaths.add(newXPaths.get(i));
						}
						
						// 更新原有路径的nextNodeIndex[]
						for (int i=0; i<xPathsSize; i++)
						{
							xPaths.get(i).updateNextNodeIndex(array[0], xPaths.get(i).getPathSize());
						}
					}
				}
			}
			in.close();
			// 读取末尾的所有非分支节点
			List<String> endNodes = new ArrayList<String>();
			String endBranchNode = null;
			in = new BufferedReader(new FileReader(filePath));
			while((str = in.readLine())!=null)
			{
				if (!str.equals(""))
				{
					
					if (numOfBranchNode == 0)
					{
						endNodes.add(str);
					}
					else
					{
						String[] array = str.split(" ");
						if (array.length > 1)
						{
							if (numOfBranchNode == 1)
							{
								endBranchNode = array[0];
							}
							numOfBranchNode--;
						}
					}
				}
			}
			in.close();

			// 为残缺路径补全末尾节点
			int xPathsSize = xPaths.size();
			int numOfEndNodes = endNodes.size();
			for (int i=0; i<xPathsSize; i++)
			{   
				if (xPaths.get(i).getPath().getEndNodeName().equals(endBranchNode))
				{
					for (int j=0; j<numOfEndNodes; j++)
					{
						SimpleCFGNode tempNode = new SimpleCFGNode();
						tempNode.setName(endNodes.get(j));
						tempNode.setType(ConstantValue.NORMAL_NODE);
						xPaths.get(i).getPath().addNode(tempNode);
					}
				}
			}
			
		}
		catch(Exception e){
			System.out.print(e.toString());
		}
		
		List<CFGPath> executedPaths = new ArrayList<CFGPath>();
		int xPathsSize = xPaths.size();
		for (int i=0; i<xPathsSize; i++)
		{
/*			System.out.println("-----------读取的路径------------");
			Iterator<SimpleCFGNode> itr = xPaths.get(i).getPath().getPath().iterator();
			while(itr.hasNext()){
				SimpleCFGNode nextNode = itr.next();
				System.out.println("CFGNode:"+nextNode.getName().toString());
				if(nextNode.isBranchNode()){
					double funValue = nextNode.getValue();
					System.out.println("value:"+nextNode.getValue());
				    System.out.println("isTrue:"+nextNode.isTrue());
				    if(!nextNode.isTrue()){
				    	funValue = -funValue;
				    }
				    if(funValue < 0){
				    	funValue = 0;
				    }
				    
	//			    fitness +=100/(1+funValue);			    
				}
			}
*/			
			executedPaths.add(xPaths.get(i).getPath());
		}
		
		return executedPaths;
	}
	
/************************************************
 | 从CFG树生成所有待测试路径						|
 | @param cfgStartNode							|
 | @return 所有路径								|
 ***********************************************/
	public static List<CFGPath> getAllPaths(CFGNode cfgStartNode)
	{
	    List<CFGPath> allPaths = new ArrayList<CFGPath>();
		CFGPath path = new CFGPath();
		List<Integer> nodeTraversed = new ArrayList<Integer>();
		
		searchPaths(allPaths, path, nodeTraversed, cfgStartNode);
		
		List<CFGPath> newAllPaths = new ArrayList<CFGPath>();
		int size = allPaths.size();
		for (int i=0; i<size; i++)
		{
			if (!isInAllPaths(newAllPaths, allPaths.get(i)))
			{
				newAllPaths.add(allPaths.get(i));
			}
		}
		
		return newAllPaths;
	}
	
	/**
	 * 路径结构体
	 * 用于从文件读取路径
	 */
	private class XPath 
	{
		private CFGPath path;
		private int[] nextNodeIndex = {0, -1};
		
		public XPath()
		{
			path = new CFGPath();
		}
		
		/**
		 * 返回路径长度
		 * @return
		 */
		public int getPathSize()
		{
			return path.getPath().size();
		}
		
		/**
		 * 获取路径
		 * @return
		 */
		public CFGPath getPath()
		{
			return path;
		}
		
		/**
		 * 添加两个坐标到nextNodeIndex[]
		 * @param index1
		 * @param index2
		 */
		private void setNextNodeIndex(int index1, int index2)
		{
			nextNodeIndex[0] = index1;
			nextNodeIndex[1] = index2;
		}
		
		/**
		 * 获取下一节点集合中较小的一个
		 * @return
		 */
		private int getMinIndex()
		{
			if (this.getSizeOfNNI() == 1)
			{
				if (nextNodeIndex[0] != -1)
					return nextNodeIndex[0];
				else
					return nextNodeIndex[1]	;
			}
			else if (this.getSizeOfNNI() == 2)
			{
				if (nextNodeIndex[0] > nextNodeIndex[1])
					return nextNodeIndex[1];
				else
					return nextNodeIndex[0];
			}
			else
				return -1;
		}
		
		/**
		 * 计算下一节点集合中的元素个数
		 * @return
		 */
		private int getSizeOfNNI()
		{
			if (nextNodeIndex[0] == -1 && nextNodeIndex[1] == -1)
				return 0;
			else if (nextNodeIndex[0] != -1 && nextNodeIndex[1] != -1)
				return 2;
			else
				return 1;
		}
		
		/**
		 * 下一节点集合是否为空
		 * @return
		 */
		public boolean hasNextNodeIndex()
		{
			if (nextNodeIndex[0] == -1 && nextNodeIndex[1]==-1)
				return false;
			else
				return true;
		}
		
		/**
		 * 名字为nodeName的节点是否在下一节点集合中
		 * @param nodeName
		 * @return
		 */
		public boolean isNextNode(String nodeName)
		{
			int pathSize = path.getPath().size();
			if (pathSize > nextNodeIndex[0] && pathSize > nextNodeIndex[1])
			{
				if (nextNodeIndex[0] != -1)
				{
					if (path.getPath().get(nextNodeIndex[0]).getName().equals(nodeName))
					{
						return true;
					}
				}
				if (nextNodeIndex[1] != -1)
				{
					if (path.getPath().get(nextNodeIndex[1]).getName().equals(nodeName))
					{
						return true;
					}
				}
			}
			else if (pathSize == nextNodeIndex[0] || pathSize == nextNodeIndex[1])
			{
				return true;
			}
			
			return false;
		}
		
		/**
		 * 更新下一节点集合
		 * @param nodeName
		 */
		public void updateNextNodeIndex(String nodeName, int maxIndex)
		{
			// 清空nextNodeIndex[]
			this.setNextNodeIndex(-1, -1);
			int count = 0;
			
			for (int i=0; i<maxIndex; i++)
			{
				if (path.getPath().get(i).getName().equals(nodeName))
				{
					nextNodeIndex[count] = i+1;
					count++;
				}
			}
		}
		
		/**
		 * 更新path和nextNodeIndex
		 * @param nodeName
		 */
		public void updateAll(String[] node)
		{			
			int pathSize = path.getPath().size();
			int sizeOfNNI = getSizeOfNNI();
			
			if (this.isNextNode(node[0]))
			{
				if (sizeOfNNI == 1)
				{
					if (nextNodeIndex[0] != -1)
					{
						if (nextNodeIndex[0] == pathSize)
						{   
							this.addNode(node);
							this.updateNextNodeIndex(node[0], path.getPath().size());
						}
						else
						{   //here
							this.updateNextNodeIndex(node[0], nextNodeIndex[0]+1);
						}
					}
					else
					{
						if (nextNodeIndex[1] == pathSize)
						{
							this.addNode(node);
							this.updateNextNodeIndex(node[0], path.getPath().size());
						}
						else
						{
							this.updateNextNodeIndex(node[0], nextNodeIndex[1]+1);
						}
					}
				}
				else if (sizeOfNNI == 2)
				{
					if (nextNodeIndex[0] == pathSize)
					{
						if (path.getPath().get(nextNodeIndex[1]).getName().equals(node[0]))
						{
							this.updateNextNodeIndex(node[0], nextNodeIndex[1]+1);
						}
						else
						{
							this.addNode(node);
							this.updateNextNodeIndex(node[0], path.getPath().size());
						}
					}
					else if (nextNodeIndex[1] == pathSize)
					{
						if (path.getPath().get(nextNodeIndex[0]).getName().equals(node[0]))
						{
							//here
							this.updateNextNodeIndex(node[0], nextNodeIndex[0]+1);
						}
						else
						{
							this.addNode(node);
							this.updateNextNodeIndex(node[0], path.getPath().size());
						}
					}
					else
					{
						if (path.getPath().get(nextNodeIndex[0]).getName().equals(node[0]))
						{
							this.updateNextNodeIndex(node[0], nextNodeIndex[0]+1);
						}
						else
						{
							this.updateNextNodeIndex(node[0], nextNodeIndex[1]+1);
						}
					}
				}
			}
			else
			{
				if (hasNextNodeIndex())
				{
					this.setNextNodeIndex(-1, -1);
				}
				else
				{
					this.updateNextNodeIndex(node[0], path.getPath().size());
				}
			}
		}
		
		/**
		 * 在path末尾添加一个新节点
		 * @param node
		 * @param paramIndex
		 */
		public void addNode(String[] node)
		{
			if (node.length == 1)
			{
				SimpleCFGNode tempNode = new SimpleCFGNode();
				tempNode.setName(node[0]);
				tempNode.setType(ConstantValue.NORMAL_NODE);
				path.addNode(tempNode);
			}
			else if (node.length == 3)
			{
				
				int pathSize = this.getPathSize();
				if (pathSize != 0 && path.getPath().get(pathSize-1).getName().equals(node[0]))
				{
					double v = Double.parseDouble(node[1]);
					path.addBranchNode(node[0], ConstantValue.BRANCH_IF, node[2], v);
				}
				else
				{

					double v = Double.parseDouble(node[1]);
					SimpleCFGNode tempNode = new SimpleCFGNode();
					tempNode.setName(node[0]);
					tempNode.setType(ConstantValue.BRANCH_IF);
					tempNode.addValue(node[2], v);
					path.addNode(tempNode);
				}
			}
		}
		
		/**
		 * 添加一个节点
		 * @param snode
		 */
		private void addNode(SimpleCFGNode snode)
		{
			this.path.getPath().add(snode);
		}
		
		/**
		 * 复制路径片段
		 * 为添加新路径做准备
		 * @return
		 */
		public XPath getNewXPath()
		{
			XPath xPath = new XPath();
			
			int minIndex = this.getMinIndex();
			
			if (minIndex != -1)
			{
				for (int i=0; i<minIndex; i++)
				{
					SimpleCFGNode snode = path.getPath().get(i);
					xPath.addNode(snode);
				}
			}
			else
			{
				xPath = null;
			}
			
			return xPath;
		}
		
		/**
		 * 判断两条路径是否相同
		 * @param xPath
		 * @return
		 */
		public boolean isSamePath(XPath xPath)
		{
			if (path.isEqual(xPath.getPath().getPath()))
			{
				return true;
			}
			else
			{
				return false;
			}
		}
	}
	
	/**
	 * 判断节点名为nodeName的节点是否在所有路径的下一节点集合中
	 * @param xPaths
	 * @param nodeName
	 * @return
	 */
	private static boolean isInNextNodes(List<XPath> xPaths, String nodeName)
	{
		int size = xPaths.size();
		for (int i=0; i<size; i++)
		{
			if (xPaths.get(i).isNextNode(nodeName))
			{
				return true;
			}
		}
		
		return false;
	}
	
	/**
	 * 添加新的路径
	 * @param xPaths
	 * @param node
	 * @return
	 */
	private static List<XPath> getNewXPaths(List<XPath> xPaths, String[] node)
	{
		List<XPath> newXPaths = new ArrayList<XPath>();
		
		int size = xPaths.size();
		for (int i=0; i<size; i++)
		{
			if (xPaths.get(i).hasNextNodeIndex())
			{
				XPath pathTemp = xPaths.get(i).getNewXPath();
				pathTemp.addNode(node);
				pathTemp.updateNextNodeIndex(node[0], pathTemp.getPathSize());
				if (!isInXPathList(newXPaths, pathTemp))
				{
					newXPaths.add(pathTemp);
				}
			}
		}
		
		return newXPaths;
	}
	
	/**
	 * 判断路径xPath是否在xPathList中
	 * @param xPathList
	 * @param xPath
	 * @return
	 */
	private static boolean isInXPathList(List<XPath> xPathList, XPath xPath)
	{
		int size = xPathList.size();
		for (int i=0; i<size; i++)
		{
			if(xPathList.get(i).isSamePath(xPath))
			{
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 判断path是否已经在allPaths中
	 * @param allPaths
	 * @param path
	 * @return
	 */
	private static boolean isInAllPaths(List<CFGPath> allPaths, CFGPath path)
	{
		int size = allPaths.size();
		for (int i=0; i<size; i++)
		{
			if (path.isEqual(allPaths.get(i).getPath()))
			{
				return true;
			}
		}
		
		return false;
	}
	
	/**
	 * 递归函数
	 * 找出当前CFG树的所有路径
	 * @param allPaths
	 * @param path
	 */
	private static void searchPaths(List<CFGPath> allPaths, CFGPath path, List<Integer> nodeTraversed, CFGNode node)
	{
		CFGPath pathTemp = path.clonePath();
		List<Integer> nodeTraversedTemp = copyNodeTraversed(nodeTraversed);
		
		if (node.getChildren() == null && node.getIfChild() == null && node.getElseChild() == null)
		{
			pathTemp.addNormalNode("node"+node.getNodeNumber(), ConstantValue.NORMAL_NODE);
			if (!nodeTraversedTemp.contains(node.getNodeNumber()))
			{
				nodeTraversedTemp.add(node.getNodeNumber());
			}
/*			
			System.out.print("-------------新的路径-----------");
			Iterator<SimpleCFGNode> itr1 = pathTemp.getPath().iterator();
			    while(itr1.hasNext()){
				    SimpleCFGNode nextNode = itr1.next();
				    System.out.println("CFGNode:"+nextNode.getName().toString());
				    if(nextNode.isBranchNode()){
				        System.out.println("isTrue:"+nextNode.isTrue());			    
				    }
			    }		
*/
			int numOfAuxiliaryVars = 0,numOfPathPredicates = 0;
			Iterator<SimpleCFGNode> itr1 = pathTemp.getPath().iterator();
		    while(itr1.hasNext()){
			    SimpleCFGNode nextNode = itr1.next();
			    if(nextNode.isBranchNode()){
			    	numOfPathPredicates += nextNode.getConstraint().getNumOfAtomicConstraint();
			    	if(nextNode.isTrue()){
			    		numOfAuxiliaryVars += nextNode.getConstraint().getNumOfAtomicConstraint()-nextNode.getConstraint().getNumOfEqualSymbol();
			    	}
			    	else
			    	{
			    		numOfAuxiliaryVars += nextNode.getConstraint().getNumOfAtomicConstraint()-nextNode.getConstraint().getNumOfNotEqualSymbol();
			    	}
			    }
		    }
		    pathTemp.setNumOfAuxiliaryVars(numOfAuxiliaryVars);
			pathTemp.setNumOfPathPredicates(numOfPathPredicates);
		    
			allPaths.add(pathTemp);	
		}
		else
		{
			if (node.getBinaryExpression() != null)	// 条件节点(if-else或者for)
			{
				Constraint constraintTemp = new Constraint(node.getBinaryExpression());
				SimpleCFGNode snode = new SimpleCFGNode("node"+node.getNodeNumber(), ConstantValue.BRANCH_IF, constraintTemp, true);
				pathTemp.addNode(snode);
				if (!nodeTraversedTemp.contains(node.getNodeNumber()))
				{
					nodeTraversedTemp.add(node.getNodeNumber());
				}
				
				if (node.getIfChild() != null)
				{
					//处理if分支
					if (nodeTraversedTemp.contains(node.getIfChild().getNodeNumber()))
					{
						if (node.getNodeNumber() > node.getIfChild().getNodeNumber())
						{
							searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getIfChild());
						}
						else
						{
							if (node.getElseChild() == null && node.getChildren() == null) 
							{
								allPaths.add(pathTemp);
							}
							else
							{
								//pathTemp.getPath().get(pathTemp.getPath().size()-1).setTrue(true);
								if (node.getElseChild() != null)
								{
									if (nodeTraversedTemp.contains(node.getElseChild().getNodeNumber()))
									{
										if (node.getNodeNumber() > node.getElseChild().getNodeNumber())
										{
											searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getElseChild());
										}
										else
										{
											allPaths.add(pathTemp);
										}
									}
									else
									{
										searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getElseChild());
									}
								}
								else
								{
									if (nodeTraversedTemp.contains(node.getChildren().get(0).getNodeNumber()))
									{
										if (node.getNodeNumber() > node.getChildren().get(0).getNodeNumber())
										{
											searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(0));
										}
										else
										{
											allPaths.add(pathTemp);
										}
									}
									else
									{
										searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(0));
									}
								}
							}
						}
					}
					else
					{   
						//pathTemp.getPath().get(pathTemp.getPath().size()-1).setTrue(true);
						//System.out.println("if分支settrue:"+pathTemp.getPath().get(pathTemp.getPath().size()-1).getName().toString());
						searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getIfChild());
					}
					
					//处理else分支
					if (node.getElseChild() != null)
					{
						pathTemp.getPath().get(pathTemp.getPath().size()-1).setTrue(false);
						//System.out.println("else分支setfalse:"+pathTemp.getPath().get(pathTemp.getPath().size()-1).getName().toString());
						if (nodeTraversedTemp.contains(node.getElseChild().getNodeNumber()))
						{
							if (node.getNodeNumber() > node.getElseChild().getNodeNumber())
							{
								
								searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getElseChild());
							}
							else
							{
								allPaths.add(pathTemp);
							}
						}
						else
						{
							searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getElseChild());
						}
						
					}
					else if (node.getChildren() != null)	//处理if-else中只有if的情况
					{
						pathTemp.getPath().get(pathTemp.getPath().size()-1).setTrue(false);
						//System.out.println("setfalse:"+pathTemp.getPath().get(pathTemp.getPath().size()-1).getName().toString());
						if (nodeTraversedTemp.contains(node.getChildren().get(0).getNodeNumber()))
						{
							if (node.getNodeNumber() > node.getChildren().get(0).getNodeNumber())
							{
								
								searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(0));
							}
							else
							{ 
								allPaths.add(pathTemp);
							}
						}
						else
						{
							searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(0));
						}
					}
				}
				else
				{
					// for条件成立
					if (nodeTraversedTemp.contains(node.getChildren().get(0).getNodeNumber()))
					{
						if (node.getNodeNumber() > node.getChildren().get(0).getNodeNumber())
						{
							searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(0));
						}
						else
						{
							if (node.getChildren().size() == 1)
							{
								allPaths.add(pathTemp);
							}
							else if (node.getChildren().size() > 1)
							{   //System.out.println("z 路径覆盖");
								pathTemp.getPath().get(pathTemp.getPath().size()-1).setTrue(true);
								if (nodeTraversedTemp.contains(node.getChildren().get(1).getNodeNumber()))
								{
									if (node.getNodeNumber() > node.getChildren().get(1).getNodeNumber())
									{
										searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(1));
									}
									else
									{
										allPaths.add(pathTemp);
									}
								}
								else
								{
									searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(1));
								}
							}
						}
					}
					else
					{
						searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(0));
					}
					
					// for条件不成立
					if (node.getChildren().size() > 1)
					{//kong
						//System.out.println("set false");
						pathTemp.getPath().get(pathTemp.getPath().size()-1).setTrue(false);
						if (nodeTraversedTemp.contains(node.getChildren().get(1).getNodeNumber()))
						{
							if (node.getNodeNumber() > node.getChildren().get(1).getNodeNumber())
							{
								
								searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(1));
							}
							else
							{
								allPaths.add(pathTemp);
							}
						}
						else
						{
							searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(1));
						}
					}
					else
					{
						pathTemp.getPath().get(pathTemp.getPath().size()-1).setTrue(false);
						allPaths.add(pathTemp);
					}
				}
			}
			else
			{
				pathTemp.addNormalNode("node"+node.getNodeNumber(), ConstantValue.NORMAL_NODE);
				
				if (!nodeTraversedTemp.contains(node.getNodeNumber()))
				{
					nodeTraversedTemp.add(node.getNodeNumber());
				}
				
				if (nodeTraversedTemp.contains(node.getChildren().get(0).getNodeNumber()))
				{
					if (node.getNodeNumber() > node.getChildren().get(0).getNodeNumber())
					{
						searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(0));
					}
					else
					{
						allPaths.add(pathTemp);
					}
				}
				else
				{
					searchPaths(allPaths, pathTemp, nodeTraversedTemp, node.getChildren().get(0));
				}
			}
		}
	}
	
	/**
	 * 拷贝出一个新的nodeTraversed
	 * @param nodeTraversed
	 * @return
	 */
	private static List<Integer> copyNodeTraversed(List<Integer> nodeTraversed)
	{
		List<Integer> nodeTraversedTemp = new ArrayList<Integer>();
		int size = nodeTraversed.size();
		for (int i=0; i<size; i++)
		{
			nodeTraversedTemp.add(nodeTraversed.get(i));
		}
		return nodeTraversedTemp;
	}
}
